package 蓝桥.模拟赛;

import java.util.HashMap;
import java.util.Map;

public class Main4_2 {
    // 存储1到n的代价
    Map<Integer,Integer> map = new HashMap<>();
    int min = Integer.MAX_VALUE;

    // 从大到小
    void backtrace(int n, int cost) {
        if(n<=0||cost>=min)
            return;
        if(n==1) {
            min = cost;
            System.out.println(n+" "+cost);
            return;
        }
        if(map.containsKey(n)&&map.get(n)<=cost)
            return;
        map.put(n, cost);

        backtrace(n-1, cost+1);

        for(int i = 1; i<10;i++){
            int t = n - i;
            // t的最大数位
            int max = 0;
            int temp = t;
            while(temp>0) {
                max = Math.max(max, temp%10);
                temp /= 10;
            }
            if(t+max == n)
                backtrace(n-i, cost+3);
        }

        if(n%2==0)
            backtrace(n/2, cost+10);
    }

    public static void main(String[] args) {
        Main4_2 m = new Main4_2();
        m.backtrace(15, 0);
        System.out.println(m.min);



    }
}
